/*
 * @lc app=leetcode id=222 lang=cpp
 *
 * [222] Count Complete Tree Nodes
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) {
            return 0;
        }
        int cnt = 0, total = 0;
        vector<TreeNode *> dq = {root};
        while(!dq.empty()) {
            vector<TreeNode *> tmp(dq.size()*2);
            int idx = 0;
            for (auto n : dq) {
                cnt++;
                if (n->left && n->right) {
                    tmp[idx++] = n->left;
                    tmp[idx++] = n->right;
                } else {
                    if (!n->left) {
                        total = 2*cnt-1;
                    } else {
                        total = 2*cnt; 
                    }
                    return total;
                }
            }
            dq = tmp;
        }
        return total;
    }
};

